/*
 * @lc app=leetcode.cn id=1579 lang=javascript
 *
 * [1579] 保证图可完全遍历
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var maxNumEdgesToRemove = function (n, edges) {
  const ufa = new UnionFind(n);
  const ufb = new UnionFind(n);
  let result = 0;

  for (const edge of edges) {
    edge[1] -= 1;
    edge[2] -= 1;
  }

  // 处理公共边
  for (const [t, v, w] of edges) {
    if (t === 3) {
      if (!ufa.union(v, w)) {
        result++;
      } else {
        ufb.union(v, w);
      }
    }
  }

  // 处理独占边
  for (const [t, v, w] of edges) {
    if (t === 1) {
      if (!ufa.union(v, w)) {
        result++;
      }
    }
    if (t === 2) {
      if (!ufb.union(v, w)) {
        result++;
      }
    }
  }

  if (ufa.count !== 1 || ufb.count !== 1) {
    return -1;
  }

  return result;
};

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x) {
    if (x !== this.parent[x]) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    let [ux, uy] = [this.find(x), this.find(y)];
    if (ux ^ uy) {
      if (this.size[ux] < this.size[uy]) {
        [ux, uy] = [uy, ux];
      }
      this.parent[ux] = uy;
      this.size[uy] += this.size[ux];
      this.count--;
      return true;
    }
    return false;
  }
}
// @lc code=end
